package binary_tree.leetcode.easy;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author Stark
 * @description 二叉树的前序遍历
 * 题目链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
 * @date 2022/4/14 10:45
 **/
public class Num144_PreorderTraversal {
    int choice = 1;
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(choice == 1) {
            //递归法
            if (root == null)
                return list;
            list.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
            return list;
        }else if(choice == 2){
            //非递归法
            if(root == null)
                return list;
            //使用栈保存二叉树结点
            Deque<TreeNode> stack = new ArrayDeque<>();
            stack.push(root);
            //当没有结点后就出循环
            while(!stack.isEmpty()){
                //取出堆顶元素,将值添加到线性表中
                TreeNode tmp = stack.pop();
                list.add(tmp.val);
                //注意,因为这里使用的栈,所以需要先存储右结点
                //注意判空
                if(tmp.right != null){
                    stack.push(tmp.right);
                }
                if(tmp.left != null){
                    stack.push(tmp.left);
                }
            }
            return list;
        }
        return null;
    }
}
